package com.c2b.algorithm.leetcode.base;

import java.util.LinkedList;
import java.util.List;

/**
 * <a href='https://leetcode.cn/problems/create-maximum-number/'>拼接最大数(Create Maximum Number)</a>
 * <p>给定长度分别为 m 和 n 的两个数组，其元素由 0-9 构成，表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数，要求从同一个数组中取出的数字保持其在原数组中的相对顺序。</p>
 * <p>求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。</p>
 * <p>说明: 请尽可能地优化你算法的时间和空间复杂度。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入:
 *          nums1 = [3, 4, 6, 5]
 *          nums2 = [9, 1, 2, 5, 8, 3]
 *          k = 5
 *      输出:
 *          [9, 8, 6, 5, 3]
 *
 * 示例 2:
 *      输入:
 *          nums1 = [6, 7]
 *          nums2 = [6, 0, 4]
 *          k = 5
 *      输出:
 *          [6, 7, 6, 0, 4]
 *
 * 示例 3:
 *      输入:
 *          nums1 = [3, 9]
 *          nums2 = [8, 9]
 *          k = 3
 *      输出:
 *          [9, 8, 9]
 * </pre>
 * </p>
 * <p>
 * <b>提示：</b>
 * <ul>
 *     <li>m == nums1.length</li>
 *     <li>n == nums2.length</li>
 *     <li>1 <= m, n <= 500</li>
 *     <li>0 <= nums1[i], nums2[i] <= 9</li>
 *     <li>1 <= k <= m + n</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/3/21 15:12
 */
public class LC0321CreateMaximumNumber_H {

    static class Solution {
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
            // nums1最少可取的数字，由nums2的长度决定。nums1最多可取的数字，由nums1的长度和k决定。
            // 如果nums1取0个，则nums2应该取k个，但nums2可能不足k个。
            int[] maxNum = new int[k];
            for (int i = Math.max(0, k - nums2.length); i <= Math.min(nums1.length, k); i++) {
                int[] candidateArr = merge(pickMax(nums1, i), pickMax(nums2, k - i));
                if (greater(candidateArr, 0, maxNum, 0)) {
                    maxNum = candidateArr;
                }
            }
            return maxNum;
        }

        /**
         * 不改变数字的相对顺序，从 nums 中选取 k 位组成的最大数字
         */
        private int[] pickMax(int[] nums, int k) {
            // 栈
            List<Integer> stack = new LinkedList<>();
            // 可丢弃的数字
            int drop = nums.length - k;
            for (int num : nums) {
                // drop > 0 && (如果栈中元素不为空) && 当前元素>栈顶元素
                while (drop > 0 && !stack.isEmpty() && num > stack.get(stack.size() - 1)) {
                    stack.remove(stack.size() - 1);
                    --drop;
                }
                stack.add(num);
            }
            int[] r = new int[k];
            for (int i = 0; i < k; i++) {
                r[i] = stack.get(i);
            }
            return r;
        }

        private int[] merge(int[] nums1, int[] nums2) {
            int[] merged = new int[nums1.length + nums2.length];
            int index1 = 0;
            int index2 = 0;
            for (int i = 0; i < merged.length; i++) {
                if (greater(nums1, index1, nums2, index2)) {
                    merged[i] = nums1[index1++];
                } else {
                    merged[i] = nums2[index2++];
                }
            }
            return merged;
        }

        /**
         * 用于比较nums1从指定位置开始的数组是否大于nums2从指定位置开始的数组
         */
        private boolean greater(int[] nums1, int index1, int[] nums2, int index2) {
            while (index1 < nums1.length && index2 < nums2.length) {
                if (nums1[index1] != nums2[index2]) {
                    return nums1[index1] > nums2[index2];
                }
                ++index1;
                ++index2;
            }
            return index2 == nums2.length;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printArrayInt(solution.maxNumber(new int[]{3, 4, 6, 5}, new int[]{9, 1, 2, 5, 8, 3}, 5));
        Printer.printArrayInt(solution.maxNumber(new int[]{6, 7}, new int[]{6, 0, 4}, 5));
        Printer.printArrayInt(solution.maxNumber(new int[]{3, 9}, new int[]{8, 9}, 3));
    }
}
